#include "src/TGPoint.h"
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <utility>
#include <limits.h> 
#include <stdint.h>

void TGPoint::set(double _x, double _y) {
    x = _x;
    y = _y;
}

double TGPoint::pdis(TGPoint& p) {

    return std::hypot(x-p.x, y-p.y);

}


TGPoint& TGPoint::operator = (const TGPoint& p) {
    x = p.x;
    y = p.y;
    return *this;
}

// bool TGPoint::operator == (const TGPoint& p)const {
//     if(fabs(x-p.x)<=EPS && fabs(y-p.y)<=EPS) {
//         return true;
//     }
//     else {
//         return false;
//     }
// }

bool TGPoint::operator < (const TGPoint& p)const {
    if(x == p.x) {
        return y < p.y;
    }
    else{
        return x < p.x;
    }
}

// bool operator==(const TGPoint& p1, const TGPoint& p2) {
//     if(fabs(p1.x-p2.x)<EPS && fabs(p1.y-p2.y)<EPS) {
//         return true;
//     }
//     else {
//         return false;
//     } 
// }

// bool operator==(TGPoint& p1, TGPoint& p2) {
//     if(fabs(p1.x-p2.x)<EPS && fabs(p1.y-p2.y)<EPS) {
//         return true;
//     }
//     else {
//         return false;
//     }
// }

TGPoint operator-(const TGPoint& p1, const TGPoint& p2) {
    TGPoint p;
    p.x = p1.x-p2.x;
    p.y = p1.y-p2.y;
    return p;
}

double TGPoint::operator * (const TGPoint& p)const{
    return x*p.x + y*p.y;
}

double TGPoint::operator^ (const TGPoint& p)const {
    return x*p.y - y*p.x;
}

TGPoint operator/(const TGPoint& p, const double& den) {
    TGPoint ret;
    ret.x = p.x / den;
    ret.y = p.y / den;
    return ret;
}

TGPoint operator+(const TGPoint& p1, const TGPoint& p2) {
    TGPoint ret;
    ret.x = p1.x + p2.x;
    ret.y = p1.y + p2.y;
    return ret;
}

const TGPoint TGPoint::operator-() const{
    return TGPoint(-x, -y);
}


double pdist(const TGPoint& p1, const TGPoint& p2) {
    double d1 = p1.x - p2.x;
    double d2 = p1.y - p2.y;
    return std::hypot(d1, d2);
}

//求两点之间的叉积
double xmul(TGPoint& p1, TGPoint& p2) {
    return p1.x*p2.y - p1.y*p2.x;
}

double xmul(const TGPoint& p1, const TGPoint& p2) {
    return p1.x*p2.y - p1.y*p2.x;
}

int dcmp(const double& x, const double& y) {
    if(fabs(x-y) < EPS) {
        return 0;
    }
    else {
        return x < y ? -1 : 1;
    }
}

bool equal(TGPoint& p1, TGPoint& p2) {
    if(dcmp(p1.x, p2.x) == 0 && dcmp(p1.y, p2.y) == 0) {
        return true;
    } 
    else {
        return false;
    }
}

bool equal(const TGPoint& p1, const TGPoint& p2) {
    if(dcmp(p1.x, p2.x) == 0 && dcmp(p1.y, p2.y) == 0) {
        return true;
    } 
    else {
        return false;
    }
}



static void _nearestPairWithDivideAndConquer(std::vector<TGPoint>& points, int l, int r, std::pair<TGPoint, TGPoint>& ret, double& d) {
    int n = r-l+1;
    if(n < 4) {
        for(int i = l; i <= r; i ++) {
            for(int j = i+1; j <= r; j ++) {
                double d1 = pdist(points[i], points[j]);
                if(d1 < d) {
                    d = d1;
                    ret.first = points[i];
                    ret.second = points[j];
                }
            }
        }
        //对点集按照y排序
        std::sort(points.begin()+l, points.begin()+r+1, [](const TGPoint& p1, const TGPoint& p2) {
            return p1.y < p2.y;
        });
    }
    else {
        int m = (r+l)>>1;
        TGPoint mp = points[m];
        _nearestPairWithDivideAndConquer(points, l, m, ret, d);
        _nearestPairWithDivideAndConquer(points, m+1, r, ret, d);
        std::inplace_merge(points.begin()+l, points.begin()+m+1, points.begin()+r+1, [](const TGPoint& p1, const TGPoint& p2){
            return p1.y < p2.y;
        });
        //存放x坐标距离mp.x 小于d的坐标
        std::vector<TGPoint> X;
        X.reserve(r-l+1);
        int xsz = 0;
        for(int i = l; i <= r; i ++) {
            if(fabs(points[i].x - mp.x) < d) {
                for(int j = xsz-1; j>=0&&fabs(points[i].y-X[j].y)<d; j--) {
                    double d1 = pdist(points[i], X[j]);
                    if(d1 < d) {
                        d = d1;
                        ret.first = points[i];
                        ret.second = X[j];
                    }
                }
                X.emplace_back(points[i]);
                xsz ++;
            }
        }
    }
    return;
}

double nearestPairWithDivideAndConquer(std::vector<TGPoint>& points, std::pair<TGPoint, TGPoint>& ret) {
    std::vector<TGPoint> pts = points;
    double d = INT32_MAX;
    //首先对点集按照x坐标值排序
    sort(pts.begin(), pts.end(), [](const TGPoint& p1, const TGPoint& p2){
        return p1.x < p2.x;
    });
    _nearestPairWithDivideAndConquer(pts, 0, points.size()-1, ret, d);
    return d;
}

double nearestPairWithBruteForce(std::vector<TGPoint>& points, std::pair<TGPoint, TGPoint>& ret) {
    double d = INT32_MAX;
    int ii = -1, jj = -1;
    int n = points.size();
    for(int i = 0; i < n; i ++) {
        for(int j = 0; j < i; j ++) {
            double dd = pdist(points[i], points[j]);
            if(dd < d) {
                d = dd;
                ii = i; jj = j;
            }
        }
    }
    ret.first = points[ii];
    ret.second = points[jj];
    return d;
}

double nearestPairWithBruteForce(std::vector<TGPoint>& points) {
    double d = INT32_MAX;
    int n = points.size();
    for(int i = 0; i < n; i ++) {
        for(int j = 0; j < i; j ++) {
            double dd = pdist(points[i], points[j]);
            if(dd < d) {
                d = dd;
            }
        }
    }
    return d;
}

bool findCircleCenterWith3Points(const TGPoint& p1, const TGPoint& p2, const TGPoint& p3, TGPoint& ans) {
    double a = p1.x - p2.x, b = p1.y-p2.y;
    double c = p1.x - p3.x, d = p1.y - p3.y;
    double e = ((p1.x*p1.x-p2.x*p2.x) - (p2.y*p2.y - p1.y*p1.y)) / 2;
    double f = ((p1.x*p1.x-p3.x*p3.x) - (p3.y*p3.y - p1.y*p1.y)) / 2;
    if(dcmp(a*d,b*c) == 0) {
        return false;
    }
    ans.x = (e*d - b*f) / (a*d - b*c);
    ans.y = (a*f - e*c) / (a*d - b*c);
    return true;
}

void minimumCoveringCircle(std::vector<TGPoint>& points, TGPoint& center, double& radius) {
    int n = points.size();
    center = points[0];
    radius = 0.0;

    //将原数据随机打乱,有效避免特殊数据卡时间复杂度
    std::random_shuffle(points.begin(), points.end());

    //判断当前点是否在圆心为center,半径为radius的圆内
    auto f = [&](TGPoint& p)->bool{
        double d = pdist(p, center);
        return d < radius;
    };
    for(int i = 1; i < n; i ++) {
        if(f(points[i])) continue;
        center = points[i];
        radius = 0.0;
        for(int j = 0; j < i; j ++) {
            if(f(points[j])) continue;
            center = (points[i]+points[j]) / 2;
            radius = pdist(points[i], points[j]) / 2;
            for(int k = 0; k < j; k ++) {
                if(f(points[k])) continue;
                findCircleCenterWith3Points(points[i], points[j], points[k], center);
                radius = pdist(center, points[k]);
            }
        }
    }
}